『Data Structures for Text Sequences』

Charles Crowley. Data Structures for Text Sequences. 1998.

Data Structures for Text Sequences

1. どんなもの？

Piece Tableの初出論文？

2. 先行研究と比べてどこがすごい？

3. 技術や手法のキモはどこ？

4. どうやって有効だと検証した？

5. 議論はある？

6. 次に読むべき論文は？

アブストラクト

文字列を保持するためのデータ構造は、テキストエディタにとって重要な部分である。本稿では、テキストシーケンスのために可能なデータ構造の範囲を調査し、評価する。テキストエディタのテキストシーケンスコンポーネントへのADTインタフェースについて調べる。6つの一般的なシーケンスデータ構造（配列、ギャップ、リスト、行ポインタ、固定サイズバッファ、ピーステーブル）を検討し、6つの構造すべてを包含するシーケンスデータ構造の一般的なモデルを示す。ピーステーブル法について詳しく説明し、その利点を示す。シーケンス・データ構造の設計空間について検討し、上記のものにいくつかのバリエーションを提示する。これらのシーケンス・データ構造を実験的に比較し、多くの基準に基づいて評価する。実験的比較は、各データ構造を編集シミュレータに実装し、何千もの編集の合成負荷を使ってテストすることによって行われる。また、合成編集負荷の生成に使用したパラメータの変化に対する結果の感受性の実験についても報告する。

https://gyazo.com/e9414d970ada3b25766422f4df2797c3

Data Structures for Text Sequences P2

Line span method

Linked List + Fixed size buffer?

検証しているデータ構造

Null

Arr(Arary(配列))

List(Linked List)

Gap(Gap Buffer)

FsbA(Fixied size buffer + 配列)

Fixied size buffer: 固定サイズバッファ

FsbAOpt(Fixied size buffer + 配列 + ItemAt最適化(?))

FsbAOpt(Fixied size buffer + Gap Buffer)

Piece(Piece Table)

PeaceOpt(Piece Table + ItemAt最適化(?))

#論文読み #論文 #文献